/*
 * Copyright (C) 2010 Jens Bierschenk
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.googlecode.algorithmlaboratory.redblacktree.timemeasure;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

import com.googlecode.algorithmlaboratory.redblacktree.RedBlackTree;

public class TimeMeasure {
	public static void main(String[] args) {
		Measurement.run(Integer.valueOf(args[0]), Integer.valueOf(args[1]));
	}
	
	private static class Measurement {
		private static final int START_RANGE = 0;
		private static final int END_RANGE = 99999999;
		private static final int DENOMINATOR = 2;
		
		private static final int BEST_CASE = 0;
		private static final int AVERAGE_CASE = 1;
		private static final int WORST_CASE = 2;
		
		private static final int TREE_SET = -1;
		private static final int RED_BLACK_TREE = -2;
		
		private static final int START_ITERATION_VALUE = 10;
		private static final long SEED = 42L;
		
		private static List<List<Integer>> bestCase;
		private static List<List<Integer>> averageCase;
		private static List<List<Integer>> worstCase;
		
		private static void init(int numberOfElements) {
			bestCase = bestCaseElements(numberOfElements, DENOMINATOR);
			averageCase = averageCaseElements(numberOfElements);
			worstCase = worstCaseElements(numberOfElements);
		}
		
		private static void run(final int toggle, final int numberOfElements){
			init(numberOfElements);
			
			if(toggle == TREE_SET){
				measureAdd(numberOfElements, WORST_CASE, new TreeSet<Integer>());
				measureAdd(numberOfElements, AVERAGE_CASE, new TreeSet<Integer>());
				measureAdd(numberOfElements, BEST_CASE, new TreeSet<Integer>());
				
				measureSearch(numberOfElements, WORST_CASE, new TreeSet<Integer>());
				measureSearch(numberOfElements, AVERAGE_CASE, new TreeSet<Integer>());
				measureSearch(numberOfElements, BEST_CASE, new TreeSet<Integer>());
			
			}else if(toggle == RED_BLACK_TREE){
				measureAdd(numberOfElements, WORST_CASE, new RedBlackTree<Integer>());
				measureAdd(numberOfElements, AVERAGE_CASE, new RedBlackTree<Integer>());
				measureAdd(numberOfElements, BEST_CASE, new RedBlackTree<Integer>());
				
				measureSearch(numberOfElements, WORST_CASE, new RedBlackTree<Integer>());
				measureSearch(numberOfElements, AVERAGE_CASE, new RedBlackTree<Integer>());
				measureSearch(numberOfElements, BEST_CASE, new RedBlackTree<Integer>());
			
			}else{
				throw new IllegalArgumentException( "wrong parameter" );
			}
		}

		private static void measureAdd(int numberOfElements, int measureCase, Set<Integer> set){
			List<List<Integer>> elements = getCaseElements(numberOfElements, measureCase, set, "Add");
			for (List<Integer> n : elements) {
				set.clear();
				
				long startLastElementAddTime = -1; long startCompleteAddTime = System.currentTimeMillis();
				for (int i = 0; i < n.size(); i++) {
					if(i == n.size() - 1)
						startLastElementAddTime = System.currentTimeMillis();
					set.add(i);
				}
				long endTime = System.currentTimeMillis();
				
				print("last element adding time:");
				print(outputTime(endTime - startLastElementAddTime, n.size(), numberOfElements));
				print("elements complete adding time:" );
				print(outputTime(endTime - startCompleteAddTime, n.size(), numberOfElements));
			}
		}
		
		private static void measureSearch(int numberOfElements, int measureCase, Set<Integer> set){
			List<List<Integer>> elements = getCaseElements(numberOfElements, measureCase, set, "Search");
			for (List<Integer> n : elements) {
				set.clear();
				set.addAll(n);
				
				long searchTimeValue = 0;
				for (Integer value : n) {
					long start = System.currentTimeMillis();
					set.contains(value);
					searchTimeValue += System.currentTimeMillis() - start;
				}
				print("elements complete search time:");
				print(outputTime(searchTimeValue, n.size(), numberOfElements));
				
				searchTimeValue = System.currentTimeMillis();
				set.contains(n.get(n.size() - 1));
				
				print("last element search time:");
				print(outputTime(System.currentTimeMillis() - searchTimeValue, n.size(), numberOfElements));
			}
		}

		private static List<List<Integer>> worstCaseElements(int numberOfElements){
			List<List<Integer>> result = new ArrayList<List<Integer>>();
			for (int i = START_ITERATION_VALUE; i <= numberOfElements; i = i * START_ITERATION_VALUE) {
				List<Integer> n = new ArrayList<Integer>();
				for(int j = 1; j <= i; j++){
					n.add(j);
				}
				result.add(n);
			}
			return result;
		}
		
		private static List<List<Integer>> averageCaseElements(int numberOfElements){
			List<List<Integer>> result = new ArrayList<List<Integer>>();
			for (int i = START_ITERATION_VALUE; i <= numberOfElements; i = i * START_ITERATION_VALUE) {
				result.add(getRandomIntegerValues(i, SEED, START_RANGE, END_RANGE));
			}
			return result;
		}
		
		private static List<List<Integer>> bestCaseElements(int numberOfElements, int denominator) {
			if(denominator <= 0 || denominator % 2 != 0){
				throw new IllegalArgumentException( "wrong denominator value" );
			}
			
			List<List<Integer>> result = new ArrayList<List<Integer>>();
			for (int i = START_ITERATION_VALUE; i <= numberOfElements; i = i * START_ITERATION_VALUE) {
				int rangeSection = Math.round(END_RANGE / denominator);
				
				List<Integer> n = new ArrayList<Integer>(); 
				n.add(Math.round(END_RANGE / 2));
				for (int j = 1; j <= denominator; j++) {
					n.addAll(getRandomIntegerValues( i / denominator, SEED, (j - 1) * rangeSection, j * rangeSection ));
				}
				n.remove(n.size() - 1);
				result.add(n);
			}
			return result;
		}
		
		private static List<Integer> getRandomIntegerValues(int size, long seed, int startRange, int endRange){
			List<Integer> result = new ArrayList<Integer>();
			
			Random random = new Random(seed);
			while(result.size() < size){
				int number = random.nextInt();
				
				if(number >= startRange && number <= endRange){
					result.add(number);
				}
			}
			return result;
		}

		private static List<List<Integer>> getCaseElements(int numberOfElements, int measureCase, Set<Integer> set, String measureMethod){
			if(numberOfElements < START_ITERATION_VALUE || numberOfElements % START_ITERATION_VALUE != 0) {
				throw new IllegalArgumentException( "wrong parameter" );
			}
			
			List<List<Integer>> elements = null;
			if(measureCase == WORST_CASE){
				elements = worstCase;
				print("-----------------------------------------------------------");
				print(measureMethod + " worst case ( " + set.getClass().getSimpleName() + " ):");
				print("-----------------------------------------------------------");
			}else if(measureCase == AVERAGE_CASE){
				elements = averageCase;
				print("-----------------------------------------------------------");
				print(measureMethod + " average case ( " + set.getClass().getSimpleName() + " ):");
				print("-----------------------------------------------------------");
			}else{
				elements = bestCase;
				print("-----------------------------------------------------------");
				print(measureMethod + " best case ( " + set.getClass().getSimpleName() + " ):");
				print("-----------------------------------------------------------");
			}
			return elements;
		}
		
		private static String outputTime(long time, int area, int numberOfElements){
			return " " + time + " ms (" + area + "/" + numberOfElements + ")";
		}
		
		private static void print(String message){
			System.out.println(message);
		}
	}
}
